package linkedlist.leetcode_23_hard;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length < 0){
            return null;
        }
        //定义优先队列，以及排序规则。
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return (o1.val - o2.val);
            }
        });
        ListNode dummyNode = new ListNode(-1);
        ListNode curNode = dummyNode;
        //把k个链表的第一个节点放入堆中
        for (int i = 0; i < lists.length; i++){
            ListNode head = lists[i];
            if(head != null){
                queue.add(head);
            }
        }
        //不断的从堆中取出节点，如果节点还有下一个节点，就把下一个节点也放入堆中。
        while(!queue.isEmpty()){
            ListNode node = queue.poll();
            curNode.next = node;
            curNode = curNode.next;
            if(node.next != null){
                queue.add(node.next);
            }
        }
        curNode.next = null;
        return dummyNode.next;
    }
}
